/**
 * 循环遍历：很明显，对原来的数组进行一次遍历很难达到目的，原因在于，遍历到某个元素A的时候，不能保证其父元素已经被遍历过了，所以这实际上是一个循环遍历的问题
 * 
处理循环遍历问题的策略是：队列数据结构，从队列尾部弹出，经过检查函数，如果符合就弹出下一个，如果不符合就放到队列头部等待下次检查；直到队列中没有元素

具体来说：

1 创建一张哈希表tree，索引为各个元素的id值
2 循环遍历队列中的元素，对每一个元素做如下处理：
3 判断此元素是否在哈希表中，如果没有的话，添加进哈希表
4 判断此元素的父元素是否在哈希表中：
(1) 如果在的话就加入到父元素的children属性中去；
(2) 如果不再的话，说明子元素在父元素之前被遍历到了，这个时候需要将此元素移动至队列头部等待下次遍历检查

 * @param {*} arr 
 * @returns 
 */
function convertArrayToTree(arr) {
  if (!Array.isArray(arr)) throw new TypeError("arr must be a array");
  const len = arr.length;
  const newArr = [...arr];
  let node = ""; // 顶点id

  // 树的属性是每一个item的id
  const tree = {};
  // 先找到顶点,也就是pid为null的
  for (let i = 0; i < len; i++) {
    if (newArr[i].pid === null) {
      newArr[i].children = [];
      tree[newArr[i].id] = newArr[i];
      node = newArr[i].id;
      // 移除顶点，因为提前找到了，不需要再遍历了
      newArr.splice(i, 1);
      break;
    }
  }

  // 利用队列，不断取出对象，判断是否有父元素，有则添加进去children,否则添加进队列等待下一次循环,直到队列元素全部清空
  while (newArr.length) {
    const _item = newArr.pop();
    const { id, pid } = _item;

    //  将id-item映射保存到记录中，方便通过id找到此元素
    tree[id] = tree[id] ?? _item;

    // 查找是否已经存在了
    if (tree[pid]) {
      if (tree[pid].children) {
        tree[pid].children.push(_item);
      } else {
        tree[pid].children = [];
        tree[pid].children.push(_item);
      }
    } else {
      // 不存在继续添加进去数组里面
      newArr.unshift(_item);
    }
  }

  return tree[node];
}

// egg:
let source = [
  {
    id: 0,
    pid: null,
    name: "document",
  },
  {
    id: 1,
    pid: 0,
    name: "body",
  },
  {
    id: 2,
    pid: 1,
    name: "title",
  },
  {
    id: 3,
    pid: 2,
    name: "div",
  },
  {
    id: 4,
    pid: 0,
    name: "html",
  },
  {
    id: 5,
    pid: 4,
    name: "div",
  },
  {
    id: 6,
    pid: 5,
    name: "span",
  },
  {
    id: 7,
    pid: 5,
    name: "img",
  },
];

console.log(convertArrayToTree(source));
